#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N_RANDOM 10
#define MAX_VALUE 100

static int num[N_RANDOM];
void insert_sort(int len, int* array);
int* copy_sample();
void swap(int* array, int pos1, int pos2);

void sort(void* (*some_sort)(int, int*));
void insert_sort(int, int*);
void shell_sort(int, int*);
void heap_sort(int, int*);
void merge_sort(int, int*);
void quick_sort(int, int*);
void bucket_sort(int, int*);
void radix_sort(int, int*);

int main(int argc, char** argv) {
	int i;
	srand(time(NULL));
	for (i = 0; i < N_RANDOM; i++) {
		num[i] = rand() % MAX_VALUE;
	}
	printArray(N_RANDOM, num);

	printf("%15s", "insert_sort :");
	sort(insert_sort);


	printf("%15s", "shell_sort  :");
	sort(shell_sort);


	printf("%15s", "heap_sort   :");
	sort(heap_sort);


	printf("%15s", "merge_sort  :");
	sort(merge_sort);


	printf("%15s", "quick_sort  :");
	sort(quick_sort);

	printf("%15s", "bucket_sort :");
	sort(bucket_sort);

	printf("%15s", "radix_sort  :");
	sort(radix_sort);
}

int* copy_sample() {
	int* array = malloc(sizeof(int) * N_RANDOM);
	int i;
	for (i = 0; i < N_RANDOM; i++) {
		*(array + i) = *(num + i);
	}
	return array;
}

void printArray(int len, int* array) {
	int i;
	for (i = 0; i < len; i++) {
		printf("%4d", *(array + i));
	}
	printf("\n");
}

void sort(void* (*some_sort)(int, int*)) {
	int *array = copy_sample();
	some_sort(N_RANDOM, array);
	printArray(N_RANDOM, array);
}

void swap(int* array, int pos1, int pos2) {
	int tmp = *(array + pos1);
	*(array + pos1) = *(array + pos2);
	*(array + pos2) = tmp;
}
// ---------insert_sort---------
void insert_sort(int len, int* array) {
	int i, j;
	int tmp;
	for (i = 1; i < len; i++) {
		tmp = *(array + i);
		for (j = i; j > 0 && tmp < * (array + j - 1); j--) {
			*(array + j ) = *(array + j - 1);
		}
		*(array + j) = tmp;
	}
}


void shell_sort(int len, int* array) {
	int gap, i, j;
	int tmp;
	for (gap = len >> 1; gap > 0; gap >>= 1) {
		for (i = gap; i < len; i++) {
			tmp = *(array + i);
			for (j = i; j >= gap && (tmp < * (array + j - gap)); j -= gap) {
				*(array + j) = *(array + j - gap);
			}
			*(array + j) = tmp;
		}
	}
}

#define leftChild(i) (2*(i)+1)
void heap_sort_sfit_down(int len, int* array, int i) {
	int child;
	int tmp = *(array + i);

	for (; leftChild(i) < len; i = child ) {
		child = leftChild(i);
		if (child + 1 < len && (*(array + child) < * (array + child + 1))) {
			child ++;
		}
		if (tmp < * (array + child))
			*(array + i) = *(array + child);
		else
			break;
	}
	*(array + i) = tmp;
}


void heap_sort(int len, int* array) {
	int i;
	// build the heap
	for (i = len >> 1; i >= 0; i--) {
		heap_sort_sfit_down(len, array, i);
	}


	// delete max
	int tmp;
	for (i = len - 1; i > 0; i--) {
		swap(array, i, 0);
		heap_sort_sfit_down(i, array, 0);
	}
}

void msort(int* array, int* tmp, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		msort(array, tmp, left, mid);
		msort(array, tmp, mid + 1, right);
		merge(array, tmp, left, mid + 1, right);
	}
}


void merge_sort(int len, int* array) {
	int *tmpArr = malloc(sizeof(int) * len);
	msort(array, tmpArr, 0, len - 1);
}


void merge(int* array, int* tmp, int lPos, int rPos, int rEnd) {
	int lEnd = rPos - 1;
	int currPos = lPos;
	int count = rEnd - lPos + 1;
	while (lPos <= lEnd && rPos <= rEnd) {
		if (*(array + lPos) <= *(array + rPos)) {
			*(tmp + (currPos++)) = *(array + (lPos++));
		} else {
			*(tmp + (currPos++)) = *(array + (rPos++));
		}
	}

	while (lPos <= lEnd) {
		*(tmp + (currPos++)) = *(array + (lPos++));
	}
	while (rPos <= rEnd) {
		*(tmp + (currPos++)) = *(array + (rPos++));
	}

	// cp tmp back
	int i = 0;
	for (i = 0; i < count; i++, rEnd-- ) {
		*(array + rEnd) = *(tmp + rEnd);
	}
}

void quick_sort(int len, int* array) {
	qqqsort(array, 0, len - 1);
}

#define cutoff (3)
void qqqsort(int* array, int left, int right) {
	if (left + cutoff < right) {
		int pivot = mid3(array, left, right);

		int i, j;
		i = left; j = right - 1;
		for (;;) {
			while (*(array + (++i)) < pivot) {}
			while (*(array + (--j)) > pivot) {}
			if (i < j) swap(array, i, j);
			else break;
		}
		swap(array, i, right - 1);
		qqqsort(array, left, i - 1);
		qqqsort(array, i + 1, right);
	} else {
		insert_sort(right - left + 1, array + left);
	}
}


int mid3(int* array, int left, int right) {
	int mid = (left + right) / 2;
	if (*(array + left) > *(array + mid)) {
		swap(array, left, mid);
	}
	if (*(array + left) > *(array + right)) {
		swap(array, right, left);
	}
	if (*(array + mid) > *(array + right)) {
		swap(array, right, mid);
	}
	swap(array, mid, right - 1);
	return *(array + right - 1);
}

void bucket_sort(int len, int*array) {
	int * bucket = malloc(sizeof(int) * MAX_VALUE);

	int i;
	// init to 0 , bzero? memset? memcpy?
	for (i = 0; i < MAX_VALUE; i++ ) {
		*(bucket + i) = 0;
	}
	for (i = 0; i < len; i++) {
		*(bucket + * (array + i)) += 1;
	}

	int j = 0;
	i = 0;
	for (j = 0; i < len && j < MAX_VALUE; j++) {
		int tmp = *(bucket + j);
		if (tmp == 0) continue;
		for (; tmp > 0; tmp--) {
			*(array + (i++)) = j;
		}
	}
}

#define BASE 10
// http://www.brpreiss.com/books/opus4/html/page518.html
void radix_sort(int len, int* array) {
	int max = *array;
	int i;
	for (i = 1; i < len; i++) {
		if (max < array[i]) max = array[i];
	}
	int exp = 1;
	int* tmpArr = malloc(sizeof(int) * len);
	while (max / exp > 0) {
		int count[BASE] = {0};
		int offset[BASE] = {0};
		// count
		for (i = 0; i < len; i++) {
			count[(array[i] / exp) % BASE] ++;
		}
		// offset
		for (i = 1; i < BASE; i++) {
			offset[i] = offset[i - 1] + count[i - 1];
		}

		int bit;
		for (i = 0; i < len; i++) {
			bit = (array[i] / exp) % BASE;
			tmpArr[offset[bit]] = array[i];
			offset[bit]++;
		}
		for (i = 0; i < len; i++) {
			array[i] = tmpArr[i];
		}
		exp *= BASE;
	}
}